package 递归回溯.二维版;

import com.alibaba.fastjson.JSON;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class No51N皇后 {

    /**
     * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
     * 上图为 8 皇后问题的一种解法。
     * 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
     * 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
     *
     * 示例：
     * 输入：4
     * 输出：[
     *  [".Q..",  // 解法 1
     *   "...Q",
     *   "Q...",
     *   "..Q."],
     *  ["..Q.",  // 解法 2
     *   "Q...",
     *   "...Q",
     *   ".Q.."]
     * ]
     * 解释: 4 皇后问题存在两个不同的解法。
     *
     * 提示：
     * 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
     */

    private int allLength;
    private boolean[] row;
    private boolean[] left;
    private boolean[] right;
    private List<List<String>> lists=new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {

        if(n==0) {
            return lists;
        }

        /**
         * 每排检测后放一个,所有都放不了,再回溯
         * 1.竖排不可放
         * 2.左斜线不可放
         * 3.右斜线不可放
         */
        this.allLength=n;
        //竖排
        this.row=new boolean[n];
        //左斜 x+y
        this.left=new boolean[2*n-1];
        //右斜 x-y+3
        this.right=new boolean[2*n-1];
        Deque<Integer> path=new ArrayDeque<>();

        dfs(0,path);

        return lists;
    }

    private void dfs(int startX,Deque<Integer> path){

        if(path.size()==allLength){
            //添加进入,默认从x=0开始
            List<String> list=new ArrayList<>(allLength);
            path.forEach(p->{
                int y=p%allLength;
                StringBuilder stringBuilder=new StringBuilder();
                for (int i = 0; i < allLength; i++) {
                    if(i!=y){
                        stringBuilder.append(".");
                    }else{
                        stringBuilder.append("Q");
                    }
                }
                list.add(stringBuilder.toString());
            });
            lists.add(list);
            return;
        }

        for (int i = 0; i < allLength; i++) {
            if(verifyXY(startX,i)){
                //通过N皇后校验
                row[i]=true;
                //x=startX y=i
                left[startX+i]=true;
                //x-y+(n-1)
                right[startX-i+allLength-1]=true;
                path.addLast(startX*allLength+i);
                dfs(startX+1,path);
                row[i]=false;
                //x=startX y=i
                left[startX+i]=false;
                //x-y+(n-1)
                right[startX-i+allLength-1]=false;
                path.removeLast();
            }
        }

    }

    private boolean verifyXY(int x,int y){
        return !row[y]&&!left[x+y]&&!right[x-y+allLength-1];
    }

    public static void main(String[] args) {
        No51N皇后 n=new No51N皇后();
        List<List<String>> lists = n.solveNQueens(4);
        System.out.println(JSON.toJSONString(lists));
    }

}
